// Created by WXX on 2021/9/13 10:21
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:

    typedef pair<int, int> PII;

    vector<vector<int>> g;
    int n, m;
    vector<vector<int>> dist;

    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        g = mat;
        n = g.size(), m = g[0].size();
        dist = vector<vector<int>>(n, vector<int>(m, 0x3f3f3f3f));
        bfs();
        return dist;
    }

    void bfs() {
        queue<PII> q;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == 0) {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        while (q.size()) {
            auto t = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int a = t.first + dx[i], b = t.second + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= m) continue;
                if (dist[a][b] > dist[t.first][t.second] + 1) {
                    dist[a][b] = dist[t.first][t.second] + 1;
                    q.push({a, b});
                }
            }
        }
    }
};

void OutputBasicArray2D(vector<vector<int>> nums) {

    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && i < nums.size()) cout << ' ';
        cout << "[";
        for (int j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ", ";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ", " << endl;
    }
    cout << "]" << endl;
}

int main() {

    vector<vector<int>> mat = {
            {0, 0, 0},
            {0, 1, 0},
            {1, 1, 1}
    };
    OutputBasicArray2D(Solution().updateMatrix(mat));

    return 0;
}
